import java.util.*;
import java.lang.*;

class VertexIterator implements Iterator
{
    Enumeration en;
    public VertexIterator(Hashtable  ht)
    {
	en = ht.keys();
    }

    public boolean hasNext () 
    {
	return en.hasMoreElements();
    }

    public Vertex next () 
    {
	Vertex v = (Vertex)en.nextElement();
	return v;
    }

    public void remove () 
    {
    }
}

class EdgeIterator implements Iterator
{
    private Enumeration en1;
    private Enumeration en2;
    private Hashtable<Vertex, Hashtable>  adjListHash;
    private Hashtable<Vertex, Edge> edgeTable;
    public EdgeIterator(Hashtable<Vertex, Hashtable>  ht)
    {
	adjListHash = ht;
	en1 = adjListHash.keys();
	if(en1.hasMoreElements())
	{
	    Vertex v = (Vertex)en1.nextElement();
	    edgeTable = adjListHash.get(v);
	    en2 = edgeTable.keys();
	}
	else
	{
	    en2 = null;
	    edgeTable = null;
	}
		
    }

    public boolean hasNext () 
    {
	if(edgeTable == null || en2 == null)
	{
	    return false;
	}
	else if(en2.hasMoreElements())
    	{
	    return true;
	}
	else 
	{
	    boolean status = false;
	    while(en1.hasMoreElements())
	    {
		Vertex v = (Vertex)en1.nextElement();
	    	edgeTable = adjListHash.get(v);
	    	en2 = edgeTable.keys();
		if(en2.hasMoreElements())
    	        {
	    	    status = true;
		    break;
		}
	    }
	    return status; 
	}
    }

    public Edge next () 
    {
	if(en2.hasMoreElements())
    	{
	    Vertex v1 = (Vertex)en2.nextElement();
	    return edgeTable.get(v1);
	}
	else 
	{
	   return null; 
	}	
    }

    public void remove () 
    {
    }
}

public class Graph<T1>
{
	    
	    	Hashtable<Vertex, Hashtable>  adjListHash;
		Hashtable <T1, Vertex> vertexTable;
		Hashtable <Vertex, Integer> visitedTable;
		public Graph()
		{
		    adjListHash = new Hashtable<Vertex, Hashtable>();
		    vertexTable = new Hashtable<T1, Vertex>();
		}		
		
		public Graph(HashSet vertexSet, HashSet edgeSet)
		{	
			adjListHash = new Hashtable<Vertex, Hashtable>();
			vertexTable = new Hashtable<T1, Vertex>();
			Iterator vertexIter = vertexSet.iterator();
			Iterator edgeIter = edgeSet.iterator();
			while(vertexIter.hasNext())
			{
			    Vertex vertex = (Vertex)vertexIter.next();
			    T1 vertexId = (T1) vertex.getVertexId();
			    vertexTable.put(vertexId, vertex);
			    Hashtable<Vertex, Edge> vertexHash  = new Hashtable<Vertex, Edge>();
			    adjListHash.put(vertex, vertexHash);
			}
			while(edgeIter.hasNext())
			{
			    Vertex vertexOne, vertexTwo;
			    Edge edge = (Edge)edgeIter.next();
			    vertexOne = edge.getVertexOne();
			    vertexTwo = edge.getVertexTwo();
			    Hashtable vertexTable = adjListHash.get(vertexOne);
			    vertexTable.put(vertexTwo, edge);
			}
		}
		
		public int getNoOfVertices()
		{
		    return adjListHash.size();
		}

		public int getNoOfEdges()
		{
		    Enumeration e = adjListHash.keys();
		    int m = 0;
		    while(e.hasMoreElements())
		    {

			Hashtable<Vertex, Hashtable> vertexTable = adjListHash.get((Vertex)e.nextElement());
			m = m + vertexTable.size();
						    
		    }
		    return m;
		}
		public int getVertexDegree(Vertex v)
		{
		    Hashtable<Vertex, Hashtable> vertexTable = adjListHash.get(v);
		    return vertexTable.size();
		}

		public Vertex getVertexNode(T1 vId)
		{
		    return vertexTable.get(vId);
		}

		public boolean isEdgeInTheGraph(Vertex v1, Vertex v2)
		{
		    boolean status = false;
		    Hashtable<Vertex, Edge> hTable = adjListHash.get(v1);
		    if(hTable != null)
		    {
		    	if(hTable.get(v2) != null)
		    	{
				status = true;
		    	}
		    }
		    return status;			
		}
		public Edge getEdgeNode(Vertex v1, Vertex v2)
		{
		    Hashtable<Vertex, Edge> hTable = adjListHash.get(v1);
		    if(hTable != null)
		    {
		    	return hTable.get(v2);	
		    }
		    return null;
		}
		public void addVertex(Vertex v)
		{
		    Vertex vertex = v;
		    vertexTable.put((T1)v.getVertexId(), vertex);
		    Hashtable<Vertex, Edge> vertexHash  = new Hashtable<Vertex, Edge>();
		    adjListHash.put(vertex, vertexHash);		    		    
		}

		public void addEdge(Edge e)
		{
		    Vertex v1, v2;
		    v1 = e.getVertexOne();
		    v2 = e.getVertexTwo();
		    Hashtable<Vertex, Edge> hTable = adjListHash.get(v1);
		    if(hTable != null)
		    {
		    	hTable.put(v2, e);
		    }
		}
		
		public void removeVertex(Vertex v)
		{
		    adjListHash.remove(v);
		    Enumeration en1 = adjListHash.keys();
		    int i = 0;
		    while(en1.hasMoreElements())
		    {
			Vertex v1 = (Vertex)en1.nextElement();	
			Hashtable<Vertex, Edge> hTable = adjListHash.get(v1);
			hTable.remove(v);
		    }
		}

		public void removeEdge(Edge e)
		{
		    Vertex v1 = e.getVertexOne();
		    Vertex v2 = e.getVertexTwo();
		    Hashtable<Vertex, Edge> hTable = adjListHash.get(v1);
		    if(hTable != null)
		    {
		    	hTable.remove(v2);	
		    }		    
		}
		    
		public Graph[] getConnectedComponents()
		{
		    Graph[] gArray = new Graph[getNoOfVertices()];
		    visitedTable = new Hashtable <Vertex, Integer>();
		    int i = 0;
		    Iterator vIter = getVertexIterator();
		    while(vIter.hasNext()) 
        	    {
			Vertex v1 = (Vertex)vIter.next();
			if(visitedTable.get(v1) != null)
			    continue;
			visitedTable.put(v1, 1);
			gArray[i] = new Graph<T1>();
			gArray[i].addVertex(v1);
			DFSTraversal(v1, gArray[i]);
			i++;
		    }
		    Graph[] ccs = new Graph[i];
		    for(int j = 0; j < i; j++)
		    {
			ccs[j] = gArray[j];
		    }
		    return ccs;		    
		}
		private void DFSTraversal(Vertex v1, Graph<T1> cc)
		{
		    Iterator vIter = getAdjacentNodesIter(v1);
		    while(vIter.hasNext()) 
        	    {
			Vertex v2 = (Vertex)vIter.next();				
			if(visitedTable.get(v2) == null)
			    cc.addVertex(v2);
			Edge e1 = getEdgeNode(v1, v2);
			cc.addEdge(e1);
			if(visitedTable.get(v2) != null)
			    continue;
			visitedTable.put(v2, 1);
			DFSTraversal(v2, cc);
		    }
		}
		public Graph[] getBiconnectedComponents()
		{
		    return null;
		}

		public Iterator getVertexIterator()
		{
		    return new VertexIterator(adjListHash);
		}

		public Iterator getEdgeIterator()
		{
		    return new EdgeIterator(adjListHash);
		}

		public Iterator getAdjacentNodesIter(Vertex v)
		{
		    Hashtable<Vertex, Hashtable> vertexTable = adjListHash.get(v);
		    return new VertexIterator(vertexTable);
		}

		public String toString()
		{
		    String s = "[ {";
		    Iterator vIter = getVertexIterator();
		    while(vIter.hasNext()) 
        	    {
			Vertex v1 = (Vertex)vIter.next();
			if(vIter.hasNext())
			{
			    s = s + v1 + ", ";
			}
			else
			{
			    s = s + v1 + "} {";
			}
		    }
		    Iterator eIter = getEdgeIterator();
		    while(eIter.hasNext()) 
        	    {
			Edge e = (Edge)eIter.next();
			if(eIter.hasNext())
			{
			    s = s + e + ", ";
			}
			else
			{
			    s = s + e;
			}
		    }
		    s = s + "} ]";
		    return s;
		}
		public String toFileFormat()
		{
		    String s = "";
		    s = s + getNoOfVertices() + " " + getNoOfEdges() + "\n";
		    Iterator eIter = getEdgeIterator();
		    while(eIter.hasNext()) 
        	    {
			Edge e = (Edge)eIter.next();
			s = s + e.getVertexOne() + " " + e.getVertexTwo() + " " + e.getWeight() + "\n";
			
		    }
		    return s;
		}
		   
}		
 

